package PAM;

import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

import Utilities.Distancematrix;

/**
 * partitioning arou8nd medoids
 * 
 * @author Mey
 *
 */
public class PAM {

	float[][] datas;
	public Distancematrix distanceMatrix;
	
	int nrEntities; 
	int nrOfClusters;
	
	public int[] vectorRelateToCluster;
	public int[] medoids;
	
	public LinkedList<LinkedList<Integer>> clustersEntities;
	
	public float[][] finalMedoids;
	
	public float cost=0;
	
	/**
	 * 
	 * @param datas first is the number of the data, second dimension the attribute
	 * @param distanceMatrix 
	 */
	public PAM(float[][] datas, Distancematrix distanceMatrix){
		this.datas=datas;
		this.nrEntities=datas.length;
		
		if(distanceMatrix != null)
			this.distanceMatrix=distanceMatrix;
		else
			this.distanceMatrix= new Distancematrix(datas);		
//		this.saveClusterData(datas, "toCluster.data");
	}
	
	public PAM(){
		
	}
	
	public void cluster(int nrOfCluster){
		this.cluster(nrOfCluster, null);
	}
	
	public void cluster(int minNrOfCluster,int maxNrOfCluster, List<Integer> idOfDataToCluster){
		PAM best;
		best= new PAM(datas, distanceMatrix);
		best.cluster(minNrOfCluster, idOfDataToCluster);
		float bestSilhouette = best.averageSilhuette();
		for(int i=minNrOfCluster+1;i<maxNrOfCluster;i++){
			PAM test= new PAM(datas, distanceMatrix);
			test.cluster(i, idOfDataToCluster);
			float testSilhouette = test.averageSilhuette();
			
			if(bestSilhouette<testSilhouette){
				best=test;
				bestSilhouette=testSilhouette;
			}
		}
		
		System.out.println("best nr of Clusters: "+best.nrOfClusters+"\tavg Silhouette: "+bestSilhouette);
		
		this.clustersEntities=best.clustersEntities;
		this.finalMedoids=best.finalMedoids;
		this.cost=best.cost;
		this.medoids=best.medoids;		
	}
	
	
	public void cluster(int nrOfCluster, List<Integer> idOfDataToCluster) {
		this.nrOfClusters = nrOfCluster;

		// silly proof

		// initialize
		vectorRelateToCluster = new int[nrEntities];
		medoids = new int[nrOfCluster];
		
		Random r = new Random();
		if(idOfDataToCluster!=null)
			randomMedoids(nrOfCluster, idOfDataToCluster);
		else
		for (int i = 0; i < nrOfCluster; i++) {
			boolean find = false;
			int e = r.nextInt(nrEntities);

			while (!find) {
				find = true;

				// proof if the only one
				for (int j = 0; j < i; j++) {
					if (medoids[j] ==e) {
						find = false;	
						continue;
					}
				}
				
				if (!find)
					// generate new if necessary
					e = r.nextInt(nrEntities);
			}
			medoids[i] = e;
		}

		//classify datas
		vectorsToMedoids(idOfDataToCluster);
		
		System.out.println("ausgangslage");
		System.out.println(Arrays.toString(medoids));
//		System.out.println(Arrays.toString(vectorRelateToCluster));
		
		
		// endless loop
		System.out.println("loop begins");
		boolean noChanges = false;
		while (!noChanges) {

			int[] newMs = bestMedoidsForCluster();

			noChanges = true;
			// proof changes
			for (int i = 0; i < nrOfCluster; i++)
				if (newMs[i] != medoids[i]) {
					noChanges = false;					
				}
			System.out.println(Arrays.toString(newMs));
			if (!noChanges){
				this.medoids = newMs;
				vectorsToMedoids(idOfDataToCluster);
//				System.out.println(Arrays.toString(vectorRelateToCluster));
			}
			System.out.println("loop");
		}		
		
		this.finalMedoids=new float[nrOfCluster][];
		for(int i=0;i<nrOfCluster;i++){
			finalMedoids[i]=datas[medoids[i]];
		}
		
	}
	
	private void randomMedoids(int nrOfCluster, List<Integer> idOfDataToCluster){
		medoids = new int[nrOfCluster];
		Random r = new Random();
		for (int i = 0; i < nrOfCluster; i++) {
			boolean find = false;
			int e = r.nextInt(idOfDataToCluster.size());

			while (!find) {
				find = true;

				// proof if the only one
				for (int j = 0; j < i; j++) {
					if (medoids[j] ==idOfDataToCluster.get(e)) {
						find = false;	
						continue;
					}
				}

				if (!find)
					// generate new if necessary
					e = r.nextInt(idOfDataToCluster.size());			
			}
			medoids[i] = idOfDataToCluster.get(e);
		}
	}
	
	private void vectorsToMedoids(){
		vectorsToMedoids(null);
	}
	
	private void vectorsToMedoids(List<Integer> idOfDataToCluster){
		
		clustersEntities= new LinkedList<LinkedList<Integer>>();
		for (int m = 0; m < nrOfClusters; m++)
			clustersEntities.add(new LinkedList<Integer>());

		if(idOfDataToCluster==null)
			for (int i = 0; i < nrEntities; i++) 
				calcAndSetClusterOfInstance(i);
		else
			for (int i = 0; i < idOfDataToCluster.size(); i++) 
				calcAndSetClusterOfInstance(idOfDataToCluster.get(i));
			
	}

	private void calcAndSetClusterOfInstance(int i) {
		// initialize
		int nearestMedoid = 0;
		float distance = distanceMatrix.getDistance(i, medoids[0]);

		// comparing
		for (int m = 1; m < nrOfClusters; m++) {
			float d = distanceMatrix.getDistance(i, medoids[m]);
			if (d < distance) {
				nearestMedoid = m;
				distance = d;
			}
		}

		// set neares Medoid
		// System.out.println(i + "\t " + nearestMedoid);
		this.vectorRelateToCluster[i] = nearestMedoid;
		clustersEntities.get(nearestMedoid).add(i);
	}
	
	private int[] bestMedoidsForCluster(){
		int[] newMedoids=new int[nrOfClusters];
		cost=0;
				
		for(int m=0;m<nrOfClusters;m++)
		{
			int bestM = -1;
			float costBest = Float.MAX_VALUE;	
			
			Iterator<Integer> itM = this.clustersEntities.get(m).iterator();			
			while(itM.hasNext()){
				
				// chose medeoid
				int M=itM.next();
				float cost=0;

				// calculate cost
				Iterator<Integer> itC = this.clustersEntities.get(m).iterator();
				while(itC.hasNext()){
					cost+= distanceMatrix.getDistance(M,itC.next());
				}
						
				// change best medeoid if necessary
				if(cost<costBest){
					costBest=cost;
					bestM=M;
				}
			}			
			// set best medeoid
			newMedoids[m]=bestM;
			cost+=costBest;
		}		
		
		System.out.println("hole cost:\t"+cost);
		
		return newMedoids;
	}
	
	public float[][] calcDistanceMatrix(float[][] datas){
		float[][] distanceMatrix = new float[datas.length][datas.length];
		
		for (int i = 0; i < datas.length; i++) {
		
			distanceMatrix[i][i] = 0;
		
			for (int j = i + 1; j < datas.length; j++) {

				float d = distance(datas[i], datas[j]);

				distanceMatrix[i][j] = d;
				distanceMatrix[j][i] = d;
			}
		}
		
//		for (int i = 0; i < datas.length; i++) 
//			System.out.println(Arrays.toString(distanceMatrix[i]));
		
		return distanceMatrix;
	}
	
	float distance(float[] one, float[] two){
		float d=0;
		
		for(int i =0; i< one.length;i++)
			d+=Math.pow(one[i]-two[i], 2);
		
		d= (float) Math.sqrt(d);
			
		
		return d;
	}
	
	public float averageSilhuette(){
		float avgS=0;
		
		for(int i=0;i<nrEntities;i++)
			avgS+=silhuette(i);
		
		avgS= avgS/nrEntities;
		
		return avgS;
	}
	
	public float silhuette(int data){
		float s=0;
		
		float a=0;
		Iterator<Integer> itC = this.clustersEntities.get(this.vectorRelateToCluster[data]).iterator();
//		int medoidVector= this.medoids[this.vectorRelateToCluster[data]];
		while(itC.hasNext()){
			a+= distanceMatrix.getDistance(data,itC.next());
		}
		 
		float minimalb= Float.MAX_VALUE;
		for (int i = 0; i < nrOfClusters; i++)//check ervery cluster
			if (i != this.vectorRelateToCluster[data]) {
				float b = 0;
				itC = this.clustersEntities.get(i)
						.iterator();
				while (itC.hasNext()) {//calc average distance
					b += distanceMatrix.getDistance(data,itC.next());
				}
				b=b/clustersEntities.get(i).size();
				if (minimalb > b)
					minimalb = b;
			}
		
		s=(minimalb-a)/Math.max(minimalb, a);
		
		
		return s;
	}
	
	public int getClassOfVector(float[] vector){
		
		// patch klassifizieren und klasse eintragen
		int nearestMedoid = 0;
		double distance = distance(vector,finalMedoids[0]);
		
		// comparing
		for (int m = 1; m < nrOfClusters; m++) {
			double d =  distance(vector,finalMedoids[m]);
			if(d<distance){
				nearestMedoid=m;
				distance=d;
			}
		}			
		return nearestMedoid;
}
	
	public boolean loadClassifier(String path){
		try {
			ObjectInputStream oo;
			
			oo = new ObjectInputStream(new BufferedInputStream(new
			FileInputStream(path)));
			
			finalMedoids=(float[][]) oo.readObject();			
			oo.close();
			
			this.nrOfClusters=finalMedoids.length;
			
			System.out.println("Number of Clusters: "+nrOfClusters);
			
//			for (int i = 0; i < emCluster.getClusterModelsNumericAtts().length; i++) {
//				TinyImageDescriptor t = new TinyImageDescriptor();
//				t.PatchToImage(emCluster.getClusterModelsNumericAtts()[i]);
//			}
			
			return true;
			
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
			return false;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
			return false;
		} catch (ClassNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
			return false;
		}
	}

	/**
	 * save a classifier
	 * @param path directory+filename
	 * @return true if it was possible to save the classifier
	 */
	public boolean saveClassifier(String path){
		
		try {
			ObjectOutputStream oo;
			
			oo = new ObjectOutputStream(new java.io.BufferedOutputStream(new
			java.io.FileOutputStream(path)));
			
			oo.writeObject(finalMedoids);
			oo.flush();
			oo.close();
			
			return true;
			
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
			return false;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
			return false;
		}
		
	}
	
	public int getNumberOfClusters(){
		return this.nrOfClusters;
	}
	
	public PAM getCopy(){
		PAM em= new PAM();
		
		em.finalMedoids=this.finalMedoids;
		em.nrOfClusters=this.nrOfClusters;
		
		return em;
	}
		
	public static void saveClusterData(float data[][],String toFile){
		try {
			ObjectOutputStream oo;

			oo = new ObjectOutputStream(new java.io.BufferedOutputStream(
					new java.io.FileOutputStream(toFile)));

			oo.writeObject(data);
			oo.flush();
			oo.close();

		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();			
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();			
		}
	}
	
	public static float[][] loadClusterData(String File){
		float[][] data;
		try {
			ObjectInputStream oo;

			oo = new ObjectInputStream(new BufferedInputStream(
					new FileInputStream(File)));

			data = (float[][]) oo.readObject();
			oo.close();
			
			return data;

		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();			
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();			
		} catch (ClassNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();			
		}
		return null;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		float[][] datas= new float[13][2];
		
		datas[0]=new float[]{0.1f,0.1f};
		datas[1]=new float[]{0.1f,0.2f};
		datas[2]=new float[]{0.2f,0.1f};
		datas[3]=new float[]{0.2f,0.2f};
		
		datas[4]=new float[]{0.8f,0.8f};
		datas[5]=new float[]{0.8f,0.9f};
		datas[6]=new float[]{0.9f,0.8f};
		datas[7]=new float[]{0.9f,0.9f};
		datas[8]=new float[]{0.85f,0.85f};
		
		
		datas[9]=new float[]{0.1f,0.8f};
		datas[10]=new float[]{0.1f,0.9f};
		datas[11]=new float[]{0.2f,0.8f};
		datas[12]=new float[]{0.2f,0.9f};
		
		
		
		PAM pam= new PAM(datas, null);
		pam.cluster(3);
		
		
		System.out.println(Arrays.toString(pam.medoids));
		System.out.println(Arrays.toString(pam.vectorRelateToCluster));
		
		System.out.println("average siluette:\t"+pam.averageSilhuette());
		System.out.println("empty distanzes:\t"+pam.distanceMatrix.findPercentageOfNotCalcDistance()+" %");
	}
	
}
